\documentclass{beamer}
\mode<presentation>
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{graphicx}

% Beamer template settings
\usetheme{Copenhagen}
\usecolortheme{crane}
\setbeamertemplate{navigation symbols}{}

\title[Dynamic Content Distribution for Mobile Enterprise Network]
{Dynamic Content Distribution for Mobile Enterprise Network}
\author{Igor Giusti da Silva \and Fábio Gomes dos Santos}
\institute{UFF - IC - Instituto de Computação}
\date{\today}
\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Descrição do problema}

\begin{frame}
  \frametitle{Sumário}
  \tableofcontents[currentsection]
\end{frame}

\subsection{Motivação}

\begin{frame}
  \frametitle{Motivação}
  \begin{itemize}
    \itemsep=0.3cm
    \item Distribuição de conteúdos corporativos
    \item Variação da demanda por um conteúdo
    \begin{itemize}
      \item Mobilidade dos usuários
      \item Popularidade dos conteúdos
    \end{itemize}
    \item Gerência dos conteúdos considera a variação de demanda
  \end{itemize}
\end{frame}

\subsection{Content Distribution Networks e Mobilidade}

\begin{frame}
  \frametitle{Content Distribution Network}

  \begin{columns}

    \begin{column}{6cm}
      \begin{itemize}
        \itemsep=0.3cm
        \item Distribui conteúdo entre servidores visando a diminuir o tráfego no backbone da rede
        \item Variação na demanda implicada pela variação da popularidade dos conteúdos
        \item Número de usuários em cada servidor tem pouca variação
        \item Período de reavaliação de configuração longos
      \end{itemize}
    \end{column}

    \begin{column}{6cm}
      \begin{figure}
        \includegraphics[scale=0.26]{images/wired_cdn.png}
      \end{figure}
    \end{column}

  \end{columns}

\end{frame}

\begin{frame}
  \frametitle{CDN Móvel}

  \begin{columns}

    \begin{column}{6cm}
      \begin{itemize}
        \itemsep=0.3cm
        \item Alteração na demanda causada por:
        \begin{itemize}
          \item Mobilidade dos usuários
          \item Variação da popularidade dos conteúdos
        \end{itemize}
        \item O número de usuários em cada servidor varia
        \item Alta frequência de reconfiguração
      \end{itemize}
    \end{column}

    \begin{column}{6cm}
      \begin{figure}
        \includegraphics[scale=0.25]{images/mobile_cdn.png}
      \end{figure}
    \end{column}

  \end{columns}

\end{frame}

\begin{frame}
  \frametitle{CDN Móvel}

  \begin{columns}

    \begin{column}{6cm}
      \begin{itemize}
        \itemsep=0.3cm
        \item Alteração na demanda causada por:
        \begin{itemize}
          \item Mobilidade dos usuários
          \item Variação da popularidade dos conteúdos
        \end{itemize}
        \item O número de usuários em cada servidor varia
        \item Alta frequência de reconfiguração
      \end{itemize}
    \end{column}

    \begin{column}{6cm}
      \begin{figure}
        \includegraphics[scale=0.25]{images/mobility.png}
      \end{figure}
    \end{column}

  \end{columns}

\end{frame}

\begin{frame}
  \frametitle{Serviço indireto}
 \begin{columns}

  \begin{column}{6 cm}
    \begin{enumerate}
      \itemsep=0.3cm
      \item Cliente faz requisição F.
      \item Conteúdo da requisição F não encontrado. Encaminha requisição.
      \item Servidor local recebe resposta de F. Encaminha resposta para cliente.
      \item Cliente recebe resposta de F.
    \end{enumerate}
  \end{column}

  \begin{column}{6 cm}
   \begin{figure}
      \includegraphics[scale=0.26]{images/indirect_service.png}
   \end{figure}
  \end{column}

 \end{columns}

\end{frame}

\begin{frame}
  \frametitle{Replicação}

\begin{columns}

  \begin{column}{6 cm}
    \begin{enumerate}
      \itemsep=0.3cm
      \item Servidor decide replicar conteúdo R e requere uma cópia de R.
      \item Servidor mais próximo recebe a requisição e responde com a cópia de R.
      \item O servidor que fez a requisição recebe resposta de R.
    \end{enumerate}
  \end{column}

  \begin{column}{6 cm}
   \begin{figure}
      \includegraphics[scale=0.30]{images/replication.png}
   \end{figure}
  \end{column}

\end{columns}

\end{frame}

\section{Simulando a MDCDN}

\begin{frame}
  \frametitle{Sumário}
  \tableofcontents[currentsection]
\end{frame}

\subsection{Informações de entrada}

\begin{frame}
  \frametitle{Constantes - Replicação, Serviço indireto e Manutenção}

  \begin{itemize}
    \itemsep=0.3cm
    \item $sr^{c}$
      \begin{itemize}
        \item Número de bytes transferidos durante uma replicação
        \item Na simulação é igual para todos os conteúdos
        \item Responsável pelo tráfego gerado por \emph{replicação} de conteúdos
      \end{itemize}

    \item $si^{c}$
      \begin{itemize}
        \item Número de bytes transferidos durante um serviço indireto
        \item Na simulação é o mesmo para todos os conteúdos
        \item Responsável pelo tráfego gerado por \emph{serviço indireto} de conteúdos
      \end{itemize}

    \item $sm^{c}$
      \begin{itemize}
        \item Número de bytes transferidos durante uma manutenção
        \item Na simulação é o mesmo para todos os conteúdos
        \item Responsável pelo tráfego gerado por \emph{manutenção} de conteúdos
      \end{itemize}

  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Constantes - Coeficientes e HW}
    %TODO - completar as descrições dos coeficientes
  \begin{itemize}
    \item $\alpha$
      \begin{itemize}
        \item Coeficiente usado no DES para suavização
        \item Durante a simulação foi usado $\alpha = 0.2$
      \end{itemize}

    \item $\delta$
      \begin{itemize}
        \item Quantidade de períodos de reconfiguração anteriores que devem ser considerados para a previsão de demanda
        \item Durante a simulação foi usado $\delta = 7$
      \end{itemize}

    \item HW
      \begin{itemize}
        \item Valor máximo de carga no servidor
        \item Cria um limite superior
        \item Durante a simulação foi usado $HW = 1000$
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Constantes - Servidor}

  \begin{itemize}
    \itemsep=0.3cm
    \item Número de servidores para a simulação: 16
    \item Todos os servidores tem posição fixa
    \item A distância pode ser representada por qualquer medida relativa de custo para transmissão
    \item A distância entre servidores não varia
    \item Todos os servidores se comunicam entre si
  \end{itemize}

\end{frame}

\begin{frame}
  \frametitle{Constantes - Servidor}
  \begin{block}{Distância entre servidores}
    A distância entre os servidores pode ser representada por uma matriz 16 x 16

    \[
    \left [ \begin{array}{cccc}
    0 & d_{1, 2} & \cdots & d_{1, 16} \\
    d_{2, 1} & 0 & \cdots & d_{2, 16} \\
    \vdots & \vdots & \ddots & \vdots \\
    d_{16, 1} & d_{16, 2} & \cdots & 0 \\
    \end{array} \right ]
    \]

    Onde $\forall (i, j),\quad (i, j) \in {\mathbb{N}^{*}}^{2} \quad e \quad (i, j) \leqslant (16, 16)$:
    \[i = j;\quad d_{i, j} = 0\]
    \[i \neq j;\quad d_{i, j} > 0\]
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Constantes - Conteúdos}

  \begin{itemize}
    \itemsep=0.3cm
    \item Numero de conteúdos para a simulação: 24
    \item Um conteúdo pode ser representado por um inteiro
    \item Cada conteúdo possui apenas um servidor de origem
  \end{itemize}

  \begin{block}{Servidores de origem}
    Podemos representar a relação de um conteúdo com seus servidores de origem
    através de um vetor de 24 posições.

    \[
      \left [ \begin{array}{ccccc}
      s_{1} & s_{2} & s_{3} & \cdots & s_{24}
      \end{array} \right ]
    \]

    Onde $s_{i} \in S$ \quad e \quad $i \in \mathbb{N^{*}} \quad e \quad i \leqslant 24$
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Variáveis - Réplicas}

  \begin{itemize}
    \itemsep=0.3cm
    \item Um servidor pode replicar ou remover conteúdos
    \item Um servidor deve saber qual é a réplica mais próxima de um conteúdo
    \item A variação de demanda requer reconfiguração dos conteúdos por parte dos servidores
    \item A reconfiguração altera a disposição de conteúdos pelos servidores
    \item A réplica mais próxima de cada conteúdo deve ser reavaliada a cada período de reconfiguração
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Variáveis - Réplicas}

  \begin{block}{Réplicas mais próximas}
    As réplicas mais próximas podem ser representadas por um vetor de 24 posições

    \[
      \left [ \begin{array}{ccccc}
      s_{1} & s_{2} & s_{3} & \cdots & s_{24}
      \end{array} \right ]
    \]

    Onde:
    \[
      s_{i} \in S \quad e \quad i \in \mathbb{N^{*}} \quad e \quad i \leqslant 24
    \]

    Se $s_{i} = servidorAtual$, então o servidor possui uma réplica do conteúdo
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Distribuições Estatísticas}

  \begin{itemize}
    \item Poisson
    \item Exponencial
    \item Zip-like
    \item Double Exponencial Smoothing
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Distribuição de Poisson}

  Na simulação descrita no artigo o tempo entre chamadas de cada usuário segue uma 			   distribuição de Poisson

  \begin{block}{Distribuição de Poisson}

    Essa distribuição representa a probabilidade de que um evento ocorra um número determinado de vezes em um intervalo de tempo, quando sabemos a média com que esses  eventos ocorrem.

    \[
    	P(X) = \frac{\lambda^{X} \cdot e^{-\lambda}}{X!}
    \]

    onde:

    \emph{X} é o número de ocorrências em um intervalo de tempo

    $\lambda$ é a média de ocorrências desse evento.

  \end{block}
\end{frame}


\begin{frame}
  \frametitle{Distribuição zip-like}

    Na simulação descrita no artigo, a popularidade dos conteúdos seguem uma distribuição zip-like com a constante $\alpha = 0,84$.

  \begin{block}{Distribuição zip-like}

    \[
      P(X) = \frac{K}{c^{\alpha}}
    \]

    onde

    \begin{itemize}
      \item \emph{X} é a requisição do conteúdo \emph{c}
      \item \emph{k} é uma constante de normalização
    \end{itemize}

  \end{block}
\end{frame}


\begin{frame}
  \frametitle{Double Exponential Smoothing}

  \begin{block}{Double Exponential Smoothing}
    Seja $y_{t}$ a atual demanda, em número de requisições, observado em um tempo \emph{t}. O método faz a predição no tempo \emph{t} de $\hat{y}_{t + \tau}$ para a demanda esperada no periodo $t + \tau$

    \[
      \hat{y}_{T + \tau}(T) =  \left ( 2 + \frac{\alpha\tau}{1 - \alpha} \right )S_{T} - \left (1 + 	      \frac{\alpha\tau}{1 - \alpha} \right )S_{T}^{[2]}
    \]

    onde:

    \[S_{T} = \alpha y_{T} + (1 - \alpha)S_{T - 1}\]
    \[S_{T}^{[2]} = \alpha S_{T} + (1 - \alpha)S_{T - 1}^{[2]}\]

  \end{block}
\end{frame}

\section{MDCDN em MPI}

\begin{frame}
  \frametitle{Sumário}
  \tableofcontents[currentsection]
\end{frame}

\subsection{Gerenciamento dos conteúdos}

\begin{frame}
  \frametitle{Cálculo dos tráfegos gerados}

  \begin{itemize}
    \item DES preve a demanda local $d^{ic}$ para o conteúdo \emph{c}
    \item Calcula-se o tráfego previsto gerado por \emph{c}
  \end{itemize}

  \begin{block}{$bi^{c}$ - Tráfego gerado pelos serviços indiretos do conteúdo \emph{c}}
    \[bi^{c} = d^{ic} \times si^{c} \times dist_{i, j}\]
  \end{block}

  \begin{block}{$br^{c}$ - Tráfego gerado pela replicação do conteúdo \emph{c}}
    \[br^{c} = sr^{c} \times dist_{i, j}\]
  \end{block}

  \begin{block}{$bm^{c}$ - Tráfego gerado pela manutenção do conteúdo \emph{c}}
    \[bm^{c} = \sum^{\delta}_{k = 1} \limits m^{t + k, c} \times sm^{c} \times dist_{i, j}\]
  \end{block}

\end{frame}

\begin{frame}
  \frametitle{Política de Pull}

  \begin{alertblock}{Premissa}
    \emph{Se o servidor não possui uma réplica do conteúdo c}
  \end{alertblock}

  \begin{block}{Decisão de Pull}
    \[
      \begin{array}{l}
        Se\: bi^{c} > (br^{c} + bm^{c})\: entao \\
        \quad Replicar\: c\: da\: replica\: mais\: proxima \\
        fim\: se
      \end{array}
    \]
  \end{block}

\end{frame}

\begin{frame}
  \frametitle{Remoção de uma réplica}

  \begin{alertblock}{Premissa}
    \emph{Se o servidor possui o conteúdo c e não é o servidor origem para c}
  \end{alertblock}

  \begin{block}{Decisão de remoção}
    \[
      \begin{array}{l}
        Se\: bi^{c} < (bm^{c})\: entao \\
        \quad Remover\: replica\: de\: c \\
        fim\: se
      \end{array}
    \]

  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Cálculo da carga do servidor}

  \begin{itemize}
    \item DES preve a demanda indireta $d^{ic}$ de cada servidor para o conteúdo \emph{c}
    \item Um vetor com as previsões para cada servidor é gerado
    \item A carga do servidor causada por serviços indiretos é a soma das posições do vetor
  \end{itemize}

  \begin{block}{Previsão da carga do servidor}
    \[
      \begin{array}{l}
        \forall j \in {S - i} \: faca \\
        \quad \forall c \in C que\: i\: possua\: faca \\
        \quad \quad d^{ic}_{j} = previsaoDemandaIndireta \\
        \quad fim\: para \\
        fim\: para \\
      \end{array}
    \]
  \end{block}

\end{frame}

\begin{frame}
  \frametitle{Cálculo da carga do servidor}

  O cálculo da carga pode gerar um vetor de cargas por conteúdo ou uma matriz de cargas \emph{c}

  \begin{block}{Vetor e matriz de carga}
    \begin{itemize}
      \item Vetor de carga $l_{servidor}$
      \[
        \begin{array}{ccccc}
          l_{1} & l_{2} & l_{3} & \cdots & l_{16}
        \end{array}
      \]

      \item Matriz de carga $l_{conteudo, servidor}$
      \[
        \left [
          \begin{array}{ccccc}
            l_{1, 1} & l_{1, 2} & l_{1, 3} & \cdots & l_{1, 16} \\
            l_{2, 1} & l_{2, 2} & l_{2, 3} & \cdots & l_{2, 16} \\
            l_{3, 1} & l_{3, 2} & l_{3, 3} & \cdots & l_{3, 16} \\
            \vdots & \vdots & \vdots & \ddots & \vdots \\
            l_{24, 1} & l_{24, 2} & l_{24, 3} & \cdots & l_{24, 16} \\
          \end{array}
        \right ]
      \]
    \end{itemize}
  \end{block}

\end{frame}

\begin{frame}
  \frametitle{Política de Push}

  Se a carga do servidor for maior que HW, o servidor deve tentar alivia-lá.

  \begin{block}{Alivio de carga}
    \[
      \begin{array}{l}
        Se\: \sum^{16}_{i = 1} carga > HW\: entao \\
        \quad Push\: do\: conteudo\: para\: o\: servidor\: que\: mais\: contribui \\
        \quad com\: a\: carga \\
        fim\: se
      \end{array}
    \]
  \end{block}

  \begin{alertblock}{Lembrete}
    \emph{A avaliação de carga acontece para cada conteúdo}
  \end{alertblock}
\end{frame}

\subsection{Sincronização entre os servidores}

\begin{frame}
  \frametitle{Tempos de reconfiguração}

  \begin{itemize}
    \item Os períodos de reconfiguração devem acontecer de forma síncrona entre os servidores
    \item O valor de um período de reconfiguração é de 10 minutos na simulação
    \item A sincronia implica no uso de MPI\_Barrier
  \end{itemize}

  \begin{figure}
    \includegraphics[scale=0.5]{images/reconfiguration.png}
  \end{figure}

\end{frame}

\begin{frame}
  \frametitle{Comunicando decisões}

  A replicação de conteúdos por um servidor pode alterar a tabela de réplicas mais próximas de outros servidores.

  \begin{exampleblock}{Solucao}
    \begin{itemize}
      \item Um servidor deve comunicar aos aos outros suas decisões
      \item MPI\_Broadcast pelo servidor que envia as decisões
      \item MPI\_Irecv pelos servidores que recebem as decisões
    \end{itemize}
  \end{exampleblock}

  \begin{alertblock}{Problema}
    Quando um servidor deve enviar suas decisões e quando deve receber as decisões de outros servidores?
  \end{alertblock}

\end{frame}

\end{document}
